package search

// 检查是否升序
func checkArrUp(arr []int) bool {
	for i := 1; i < len(arr); i++ {
		if arr[i] < arr[i-1] {
			return false
		}
	}
	return true
}

// 检查是否降序
func checkArrDown(arr []int) bool {
	for i := 1; i < len(arr); i++ {
		if arr[i] > arr[i-1] {
			return false
		}
	}
	return true
}

// 检查是否先升后降
func checkArrUpToDown(arr []int) bool {
	for i := 1; i <= len(arr)-1; i++ {
		if checkArrUp(arr[0:i]) && checkArrDown(arr[i:]) {
			return true
		}
	}
	return false
}

// 检查是否先升后降2
func checkArrUpToDown2(arr []int) bool {
	i := 1
	j := len(arr) - 1
	flag1 := true
	flag2 := true
	for i < j {
		if arr[i] >= arr[i-1] {
			i++
		} else {
			flag1 = false
		}

		if arr[j-1] >= arr[j] {
			j--
		} else {
			flag2 = false
		}

		if !flag1 && !flag2 {
			break
		}
	}
	return i >= j && i != 1 && j != len(arr)-1
}

// 检查是否先降后升
func checkArrDownToUp(arr []int) bool {
	for i := 1; i < len(arr)-1; i++ {
		if checkArrDown(arr[0:i]) && checkArrUp(arr[i:]) {
			return true
		}
	}
	return false
}

// 检查是否先降后升2
func checkArrDownToUp2(arr []int) bool {
	i := 1
	j := len(arr) - 1
	flag1 := true
	flag2 := true
	for i < j {
		if arr[i] <= arr[i-1] {
			i++
		} else {
			flag1 = false
		}

		if arr[j-1] <= arr[j] {
			j--
		} else {
			flag2 = false
		}

		if !flag1 && !flag2 {
			break
		}
	}
	return i >= j && i != 1 && j != len(arr)-1
}

//  顺序查找，找到了返回在数组的下标
func sequentialSearch(arr []int, target int) (index, times int) {
	length := len(arr)
	for i := 0; i < length; i++ {
		if arr[i] == target {
			return i, i + 1
		}
	}
	return -1, length
}

// 二分查找，找到了返回在数组中的下标，否则返回-1
func binarySearch(arr []int, target int) (index, times int) {
	l, r := 0, len(arr)-1
	times = 0
	//在arr[l...r]中查找target
	for l <= r {
		middleIndex := l + (r-l)/2
		times++
		if arr[middleIndex] == target {
			return middleIndex, times
		} else if arr[middleIndex] > target {
			r = middleIndex - 1
		} else {
			l = middleIndex + 1
		}
	}
	return -1, times
}

// 三分查找，找到了返回在数组的下标
func thirdSearch(arr []int, target int) (index, times int) {
	low := 0
	high := len(arr) - 1
	times = 0
	//循环的终止条件
	for low <= high {
		// 初始化枢轴
		mid1 := low + (high-low)/3
		mid2 := high - (high-low)/3
		// 枢轴
		midData1 := arr[mid1]
		midData2 := arr[mid2]
		times++

		if midData1 == target {
			return mid1, times
		} else if midData2 == target {
			return mid2, times
		}

		if midData1 < target {
			low = mid1 + 1
		} else if midData2 > target {
			high = mid2 - 1
		} else {
			low = low + 1
			high = high - 1
		}
	}
	return -1, times
}

//  插值查找
func interpolationSearch(arr []int, target int) (index, times int) {
	l := 0
	r := len(arr) - 1
	times = 0
	//循环的终止条件
	for l <= r {
		// 大段
		leftv := float64(target - arr[l])

		// 整段
		allv := float64(arr[r] - arr[l])

		// 整段差
		diff := float64(r - l)

		// 计算中间值
		mid := int(float64(l) + diff*leftv/allv)
		// 次数加一
		times++

		if mid < 0 || mid >= len(arr) {
			return -1, times
		}

		if arr[mid] > target {
			r = mid - 1
		} else if arr[mid] < target {
			l = mid + 1
		} else {
			return mid, times
		}
	}
	return -1, times
}

var timesInsert int = 0

//  插值查找
func interpolationSearch2(arr []int, target int, low int, high int) (index int) {
	if low > high {
		return -1
	}
	timesInsert++
	mid := low + (target-arr[low])/(arr[high]-arr[low])*(high-low)
	if arr[mid] == target {
		return mid
	} else if arr[mid] > target {
		return interpolationSearch2(arr, target, low, mid-1)
	} else {
		return interpolationSearch2(arr, target, mid+1, high)
	}
}

// 查找第 k 小的数: 蛮力法
func bruteForce(arr []int, k int) (value, times int) {
	length := len(arr)
	minIndex := 0
	times = 0
	flag := make([]bool, 10)
	for k > 0 {
		for i := 1; i < length; i++ {
			times++
			if !flag[i] && arr[minIndex] > arr[i] {
				minIndex = i
			}
		}
		value = arr[minIndex]
		flag[minIndex] = true
		k--
		minIndex = 0
	}
	return value, times
}

// 查找第 k 小的数: 预排序
func preSort(arr []int, k int) (value, times int) {
	nums := make([]int, 10)
	// 拷贝
	copy(nums, arr)
	// 使用快速排序
	times = quickSort(nums)

	return nums[k-1], times
}

// 查找第 k 小的数: 减可变规模
func subtractVariableSize(arr []int, k int) (value, times int) {
	return quickSelect(arr, 0, len(arr)-1, k), count2
}

// 快查比较次数统计变量
var count2 int

func lomutoartition(nums []int, start int, end int) int {
	p := nums[start]
	s := start
	for i := start + 1; i <= end; i++ {
		if nums[i] < p {
			s++
			swap(nums, s, i)
		}
	}
	swap(nums, start, s)
	return s
}

// 快查（快排思想）
func quickSelect(nums []int, start int, end int, k int) int {
	count2++
	s := lomutoartition(nums, start, end)
	if s == start+k-1 {
		return nums[s]
	} else if s > start+k-1 {
		return quickSelect(nums, start, s-1, k)
	} else {
		return quickSelect(nums, s+1, end, start+k-1-s)
	}
}

// 二分查找求先升后降数列最大值
func binaryGetMax(nums []int) (max int, times int) {
	times = 0
	if nums == nil {
		return -1, times
	}
	left := 0
	right := len(nums) - 1
	for left < right {
		times++
		mid := left + (right-left)/2
		if nums[mid] > nums[mid+1] {
			right = mid
		} else if nums[mid] < nums[mid+1] {
			left = mid + 1
		} else {
			if nums[left] > nums[right] {
				right--
			} else {
				left++
			}
		}
	}
	return nums[left], times
}

// 三分查找求先升后降数列最大值
func trisectionSearchMax(nums []int) (max int, times int) {
	times = 0
	if nums == nil {
		return -1, times
	}
	left := 0
	right := len(nums) - 1

	for left < right {
		times++
		midl := left + (right-left)/3
		midr := right - (right-left)/3
		if nums[midl] > nums[midr] {
			right = midr - 1
		} else {
			left = midl + 1
		}
	}
	return nums[left], times
}
